package com.cuz.daileetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * @description:
 *
 * 448. 找到所有数组中消失的数字
 * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
 * 示例 1：
 * 输入：nums = [4,3,2,7,8,2,3,1]
 * 输出：[5,6]
 * 示例 2：
 * 输入：nums = [1,1]
 * 输出：[2]
 * 提示：
 * n == nums.length
 * 1 <= n <= 105
 * 1 <= nums[i] <= n
 * 进阶：你能在不使用额外空间且时间复杂度为 O(n)
 * 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
 * @author cuzz
 * @date 22:51 2021/10/5
 * @version 1.0
 **/
public class Day17_3 {
    static class S1{
        public static void main(String[] args) {
            System.out.println(findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
        }
        public static List<Integer> findDisappearedNumbers(int[] nums) {
            //4,3,2,7,8,2,3,1
            //4 3 2 -7 8 2 3 1
            //4 3 -2 -7 8 2 3 1
            //4 -3 -2 -7 8 2 3 1
            //4 -3 -2 -7 8 2 3 -1
            //-4 -3 -2 -7 8 2 -3 -1
            //第一次循环：
            // 如果取到数字x  取其绝对值 abs(x) 将 num[ abs(x)-1]的值置为-abs(num[ abs(x)])
            //第二次循环
            //遍历到index num[index]>0 那么index+1 是答案之一
            LinkedList<Integer> res = new LinkedList<>();
            for (int index = 0; index < nums.length; index++) {
                int temp=Math.abs(nums[index])-1;
                nums[temp]=-Math.abs(nums[temp]);
            }
            for (int index = 0; index < nums.length; index++) {
                if (nums[index]>0){
                    res.add(index+1);
                }
            }
            return res;
        }

    }
}
